1 Списковые объекты

Каждый тип объекта предназначен для решения определенного типа задачи. Вектор обеспечивает случайный доступ к элементам. В тоже время операции вставки и удаления выполняются крайне неэффективно. Последние операции эффективно выполняются объектами из семейства список. Но, у последних объектов как раз случайный доступ выполняется неэффективно (за что то нужно расплачиваться). У данного объектов есть и другие недостатки, который мы обсудим в следующей заметке.

1.1 Список

Возвращаясь к семейству векторных объектов. В частности, объекты vector/array обеспечивают через индекс быстрый случайный доступ к любому элементу. Например, если мы хотим изменить значение элемента с индексом $3$ в целочисленном векторе a,

то достаточно сделать следующее:

Таким образом данная операция делается достаточно просто и эффективно. Но, вставка/удаление элемент из середины вектора будет выполнена крайне неэффективно: при каждой такой операции будут перекопированы множество элементов (от данного к концу).

Создание По аналогии с векторами список элементов заданного типа создается так:

Элементы в список можно добавлять таким же образом как и в вектор, т.е.

Добавит число 5 в концу списка.

Цикл по элементам Допустим нам нужно выполнить некоей действие для всех элементов списка. Для векторов было справедливо:

У списков нет возможности получить доступа к элементу с заданным индексом. Если данную операцию реализовать, то она будет крайне неэффективной (будем пробегать все элементы до заданного).

Так же напомню, что по массивам можно организовать проход по элементам следующим образом:

В связи со списками появляется новый тип сущности: итератор. Это объект, который позволяет пробежаться по всем элементам списка (не обращаясь к ним по индексу). Последнее делается так:

В первой строчке создается объект (итератор), который как раз и используется для обхода всех элементов списка.

В цикле for производится инициализация данной переменной начальным значением. Для этого используется метод begin объекта список.

Операция перехода к следующему элементу достигается за счет операции ++, т.е. прибавления к объекту итератор 1. Иначе говоря, можно было бы написать

Вообще в общем случае,

соответствует переходу к элементу на n позиций вперед.

Условие завершение цикла заключается в проверки того достигли ли мы конца. Концевому элементу соответствует значение возвращаемое методом end.

Доступ к значению самого элемента получается по аналогии с Сишными указателями – за счет разыменования, т.е. использования оператора звездочка.

Самым важным является то, то для вектором сработает тот же самый код. Таким образом, использование итераторов позволяет обобщить проход по всем элементам.

Не по всем элементам Если нужно обойти не все элементы, а например начиная с третьего, до предпоследнего, то пишем:

Следует иметь ввиду, что сама операция перехода к заданному элементу может быть и не столь эффективна. Она фактически может оказаться эквивалентной по-элементному проходу. Так, для вектором данная операция будет эффективной (просто передвигается указатель), а для списков не эффективной (придется пробежаться по цепочке элементов).

По всем элементам Если же нужно обойти все элементы (с первого по последний), то можно цикл записать ещё короче:

Здесь переменная a (пишется до двоеточия) используется для обхода всех элементов b (пишется после двоеточия). У переменной a Также указан тип данных. Тип int может использоваться для считывания элементов, например, для их печати.

Для того чтобы иметь возможность поменять значение элемента, нужно поменять тип данных на ссылочный. Тогда:

Данный код возведет все элементы вектора в квадрат.

Вставка элемента

1.2 Алгоритмы

В стандартной STL библиотеки имеется большое количество функций для обработки элементов объектов: поиск, по-элементная операция, сортировка, фильтрация и другие. Они в основном оперируют как раз итератором.

Поиск элемента Можно самостоятельно написать код:

Найдя значение итератора можно выполнить какую либо операцию. Например, добавит к элементу значение 100:

или вставить значение:

Но суть не в этом.

Суть в том, что вместо того, чтобы писать собственную функцию поиска элемента, можно было бы воспользоваться готовой функцией find:

Последнее позволило сократить код.

Указывается начальным и последний элемент.

Такие функции существую для разных важных действий.

Произвольный предикат Помимо писка конкретного элемента можно при поиске применить произвольный предикат. Предикат это функция, которая возвращает значение истинности.

Например, если нужно найти первое число делящееся на $3$, то можно воспользоваться следующим предикатом.

Тогда, необходимо вызвать функцию find_if передав в качестве последнего аргумента имя функции.

Подсчет количества Допустим, нужно посчитать количество элементов равных заданному.

Так, если нужно посчитать количество элементов равных $2$, то можно написать код:

По аналогии с find_if можно написать код, который подсчитывает количество элементов для которых истинен предикат:

Выполнить действие для всех элементов Полным аналогом классического цикла for можно считать алгоритм for_each.

Ламбда функция Более того, можно воспользоваться ламбда функцией:

В более расширенном варианте можно использовать и внешние переменные, т.е. переменные не ходящие в состав аргументов. Например:

Замечу, что переменная e перечислена в квадратных скобках. При таком способе, переменная доступна только на чтение. При попытке записать в неё значение будет выдана ошибка.

При необходимости возможности модификации внешних переменных необходимо воспользоваться модификатором ссылка (&):

Сортировка Существуют ряд функций, который преобразуют массив в целом. В ним относится сортировка. Сам объект (например list) может иметь более эффективную реализацию. Но можно сортировать и с функцией sort.